import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by JiaJia on 2019/5/21 0021.
 * 数据流中的中位数
 * 用大顶堆保存小的那一半数字，用小顶堆保存大的那一半数字
 * 用优先队列建堆
 */
public class Code64 {
   //大顶堆
    private PriorityQueue<Integer> left = new PriorityQueue<>(16, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
    //小顶堆
    private PriorityQueue<Integer> right = new PriorityQueue<>();
    private int N=0;
    public void Insert(Integer val){
        if (N%2==0){
            left.add(val);
            right.add(left.poll());
        }else {
            right.add(val);
            left.add(right.poll());
        }
        N++;
    }
    public Double GetMedian(){
        if (N%2==0){
            return (right.peek()+left.peek())/2.0;
        }else {
            return (double)right.peek();
        }
    }
}